package LeetCode.leetcode450;


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
//    public TreeNode deleteNode(TreeNode root, int key) {
//        if (root == null)
//            return null;
//        if (root.val == key) {
//            //找到要删除的点
//            if (root.left == null && root.right == null) {
//                return null;
//            } else if (root.right != null && root.left == null) {
//                return root.right;
//            } else if (root.left != null && root.right == null) {
//                return root.left;
//            } else {
//                //左右子树都不为空
//                TreeNode tmp = root.right;
//                while (tmp.left != null) {
//                    tmp = tmp.left;
//                }
//                tmp.left = root.left;
//                root.right = deleteNode(root.right,tmp.val);
//            }
//        } else {
//            //当前节点不是key值
//            if (root.val > key) {
//                root.left = deleteNode(root.left, key);
//            } else {
//                root.right = deleteNode(root.right, key);
//            }
//        }
//        return root;
//    }
public TreeNode deleteNode(TreeNode root, int key) {
    root = delete(root,key);
    return root;
}

    private TreeNode delete(TreeNode root, int key) {
        if (root == null) return null;

        if (root.val > key) {
            root.left = delete(root.left,key);
        } else if (root.val < key) {
            root.right = delete(root.right,key);
        } else {
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;
            TreeNode tmp = root.right;
            while (tmp.left != null) {
                tmp = tmp.left;
            }
            root.val = tmp.val;
            root.right = delete(root.right,tmp.val);
        }
        return root;
    }
}
